import SortMoudle
#树所用的节点
class TreeNode:
    def __init__(self,data,leftChild=None,rightChild=None,fatherNode=None):
        self.data = data
        self.leftChild = leftChild
        self.rightChild = rightChild
        self.fatherNode = fatherNode

#树的父类
class TreeBase():
    def __init__(self):
        self.root=None
    #创建一个完全二叉树
    def CreateTree(self,arr,rootPos=0):
        if not rootPos < len(arr):
            return
        #print(rootPos)
        node = TreeNode(arr[rootPos])
        node.leftChild = self.CreateTree(arr,rootPos * 2 + 1)
        node.rightChild = self.CreateTree(arr,rootPos * 2 + 2)
        self.root = node
        return self.root
#树的前、中、后序遍历
#region 树的前、中、后序和层序遍历
    def PreOrder(self):
        if self.root == None:
            return
        #pass
        print(self.root.data,end = ",")
        PreOrder(self.root.leftChild)
        PreOrder(self.root.rightChild)
    #后序遍历
    def PostOrder(self):
        if self.root == None:
            return
        PostOrder(self.root.leftChild)
        PostOrder(self.root.rightChild)
        print(self.root.data,end = ",")

    #中序遍历
    def MidOrder(self):
        if self.root == None:
            return
        MidOrder(self.root.leftChild)
        print(self.root.data,end = ",")
        MidOrder(self.root.rightChild)

    #层序遍历
    def LevelOrder(self):
        list = []
        listIndex = 0
        list.append(self.root)
        while(listIndex<len(list)):
            print("%d,"%(list[listIndex].data),end = "")
            if list[listIndex].leftChild != None:
                list.append(list[listIndex].leftChild)
            if list[listIndex].rightChild != None:
                list.append(list[listIndex].rightChild)
            listIndex = listIndex+1
            
        #listIndex = 0;
        #listLen = len(list)
        #while(listIndex<listLen):

    #以树状格式打印出树
    def PrintTree(self):

        if self.root == None:
            print("No Tree")
            return
        list = []
        listIndex = 0
        list.append(self.root)
        while(listIndex<len(list)):
            if list[listIndex].leftChild != None:
                list.append(list[listIndex].leftChild)
            if list[listIndex].rightChild != None:
                list.append(list[listIndex].rightChild)
            listIndex = listIndex+1
    
        treeCount = listIndex*2

        list = []
        listIndex = 0
        list.append(self.root)

        while(listIndex<treeCount):
            #print("%d,"%(list[listIndex].data),end = "")
            #if list[listIndex].data != "  " and ((list[listIndex].leftChild != None) or (list[listIndex].rightChild != None)):
            #if list[listIndex].data != "  ":
            if list[listIndex].leftChild != None:
                list.append(list[listIndex].leftChild)
            else:
                list.append(TreeNode("  "))
            if list[listIndex].rightChild != None:
                list.append(list[listIndex].rightChild)
            else:
                list.append(TreeNode("  "))
            listIndex = listIndex+1

        listIndex = 0
        listLen = len(list)
        listMaxNum = (listLen+1)/2
        #listMaxNum = (listLen+1)
        levelNum = 0
        levelMax = 1
        #print(listMaxNum)

        while(listIndex<listLen):
            levelNum = levelNum + 1
            speaceNum = listMaxNum*3/2

            i = 0
            while(i<speaceNum-3):
                print(" ",end = "")
                i = i + 1
            print("%3s"%(list[listIndex].data),end = "")
            i =0
            while(i<speaceNum):
                print(" ",end = "")
                i = i + 1
            listIndex = listIndex + 1
        
            if levelNum < levelMax:
                pass
            else:
                listMaxNum = listMaxNum/2
                levelMax = levelMax*2
                levelNum = 0
                print("")
                speaceNum = listMaxNum*3/2
        print("")
    
    #endregion


#定义我的平衡二叉树
class MyBinaryTree:
    #从一个数组创建一棵平衡二叉树
    def CreateBlanceBinaryTree(arr):
        i = 0
        while(i < longth):
            nodeTemp = TreeNode(arr[i])
            MyBinaryTree.AddNodeInBlanceSearchTree(root,nodeTemp)
            i = i + 1
        return root

    #给一个二叉查找树添加一个节点
    def AddNodeInBlanceSearchTree(root,node,rootFather=None):
        if root == None:
            root = node
            return root
        
        #判断新加入数据比当前节点大，放到右子树那边
        if node.data > root.data:
            root.rightChild = MyBinaryTree.AddNodeInBlanceSearchTree(root.rightChild,node,root)
        else:
            root.leftChild = MyBinaryTree.AddNodeInBlanceSearchTree(root.leftChild,node,root)

        
        #判断插入节点之后是否树不平衡了
        leftHeight = MyBinaryTree.GetHeight(root.leftChild)
        rightHeight = MyBinaryTree.GetHeight(root.rightChild)

        #如果左子树深度比右子树大1
        if leftHeight - rightHeight > 1:
            if node.data > root.leftChild.data:
                #双旋转
                root = MyBinaryTree.LR(root,rootFather)
                pass
            else:
                #单旋转
                root = MyBinaryTree.LL(root,rootFather)
                pass
        else:
            #如果右子树深度比左子树大1
            if rightHeight - leftHeight > 1:
                if node.data > root.rightChild.data:
                    root = MyBinaryTree.RR(root,rootFather)
                    pass
                else:
                    root = MyBinaryTree.RL(root,rootFather)
                    pass
            else:
                #此时树应该使平衡的
                pass

        return root

    #获取一棵树的高度
    def GetHeight(root):
        #如果根节点不存在返回0
        if root == None:
            return 0
        #因为不知道左子树或者右子树是否存在，暂定其高度为0
        leftChildHeight = 0
        rightChildHeight = 0
        
        #判断左子树是否存在，存在了对左子树求高度
        if root.leftChild == None:
            pass
        else:
            leftChildHeight = MyBinaryTree.GetHeight(root.leftChild)
        #判断右子树是否存在，存在了对右子树求高度
        if root.rightChild == None:
            pass
        else:
            rightChildHeight = MyBinaryTree.GetHeight(root.rightChild)
        #返回两课子树里面较高的那棵树的高度+1，加的这个1是根节点的高度
        if leftChildHeight > rightChildHeight:
            return leftChildHeight + 1
        else:
            return rightChildHeight + 1

    #平衡二叉树的旋转
    #region 
    #单左旋 左小右大的树
    def LL(root,rootFather):
        print("Enter LL")

        PrintTree(root)


        rootTemp = root
        root = root.leftChild

        rootTemp.leftChild = root.rightChild
        root.rightChild = rootTemp

        if rootFather == None:
            pass
        else:
            if root.data > rootFather.data:
                rootFather.rightChild = root
            else:
                rootFather.leftChild = root
        return root

    #左右双旋 左小右大的树
    def LR(root,rootFather):
        print("Enter LR")
        PrintTree(root)
        rootTemp = root
        rootLeftTemp = root.leftChild
        
        #一次旋转
        root.leftChild = root.leftChild.rightChild
        rootLeftTemp.rightChild = root.leftChild.leftChild
        root.leftChild.leftChild = rootLeftTemp

        #第二次旋转
        root = root.leftChild
        rootTemp.leftChild = root.rightChild
        root.rightChild = rootTemp

        #和root的父节点联系起来
        if rootFather == None:
            pass
        else:
            if root.data > rootFather.data:
                rootFather.rightChild = root
            else:
                rootFather.leftChild = root
        return root
    
    #单右旋 左大右小的树
    def RR(root,rootFather):
        print("Enter RR")
        PrintTree(root)
        rootTemp = root
        root = root.rightChild

        rootTemp.rightChild = root.leftChild
        root.leftChild = rootTemp

        if rootFather == None:
            pass
        else:
            if root.data > rootFather.data:
                rootFather.rightChild = root
            else:
                rootFather.leftChild = root
        return root

    #右左双旋 左大右小树
    def RL(root,rootFather):
        print("Enter RL")
        PrintTree(root)
        rootTemp = root
        rootRightTemp = root.rightChild

        #一次旋转
        root.rightChild = root.rightChild.leftChild
        rootRightTemp.leftChild = root.rightChild.rightChild
        root.rightChild.rightChild = rootRightTemp

        #第二次旋转
        root = root.rightChild
        rootTemp.rightChild = root.leftChild
        root.leftChild = rootTemp

        #和root的父节点联系起来
        if rootFather == None:
            pass
        else:
            if root.data > rootFather.data:
                rootFather.rightChild = root
            else:
                rootFather.leftChild = root
        return root
    #endregion
    
    #检查一个节点是否是叶子节点，如果是则返回True，不是则返回False
    def CheckIsLeafNode(node):
        if node.leftChild == None and node.rightChild == None:
            return True
        else:
            return False


    #从一颗平衡二叉树中删除一个节点
    def DelNode(nodeData,root,rootFather=None):
        if root == None:
            print("没能找到要删除的节点")
            return None

        #如果root就是需要删除的点
        if nodeData.data == root.data:
            #如果左节点不为空
            if root.leftChild!=None:
                #如果左孩子不空，且右孩子不空
                if root.rightChild!=None:
                    #判断树的高度决定从那里删除
                    leftHeight = MyBinaryTree.GetHeight(root.leftChild)
                    rightHeight = MyBinaryTree.GetHeight(root.rightChild)
                    #如果左子树高度高于右子树，从左子树里删除
                    if leftHeight>rightHeight:
                        rootLeftRoot = root.leftChild
                        rootLeftFather = root
                        #循环找到左子树最右边那个节点
                        while(rootLeftRoot.rightChild!=None):
                            rootLeftFather = rootLeftRoot
                            rootLeftRoot = rootLeftRoot.rightChild
                        if rootLeftRoot.data>rootLeftFather.data:
                            rootLeftFather.rightChild = MyBinaryTree.DelNode(rootLeftRoot,rootLeftRoot)
                        else:
                            rootLeftFather.leftChild = MyBinaryTree.DelNode(rootLeftRoot,rootLeftRoot)
                        root.data = rootLeftRoot.data
                    #如果右子树高度高于左子树，从右子树里删除
                    else:
                        rootRightRoot = root.rightChild
                        rootRightFather = root
                        #循环找到左子树最右边那个节点
                        while(rootRightRoot.leftChild!=None):
                            rootRightFather = rootRightRoot
                            rootRightRoot = rootRightRoot.leftChild
                        if rootRightRoot.data>rootRightFather.data:
                            rootRightFather.rightChild = MyBinaryTree.DelNode(rootRightRoot,rootRightRoot)
                        else:
                            rootRightFather.leftChild = MyBinaryTree.DelNode(rootRightRoot,rootRightRoot)
                        root.data = rootRightRoot.data
                        pass
                    pass
                #如果左孩子不空，右孩子为空
                else:
                    root = root.leftChild
            #如果左孩子为空
            else:
                #如果右孩子不为空（左节点为空）
                if root.rightChild!=None:
                    root = root.rightChild
                #如果右孩子为空（左节点为空）,该节点是叶子节点
                else:
                    root = None

        #如果root不是需要删除的点
        else:
            if nodeData.data>root.data:
                root.rightChild = MyBinaryTree.DelNode(nodeData,root.rightChild,root)
                #需要判断平衡状态
                leftHeight = MyBinaryTree.GetHeight(root.leftChild)
                rightHeight = MyBinaryTree.GetHeight(root.rightChild)

                #不平衡需要旋转（因为从一个平衡二叉树的右子树删除一个节点，不需要考虑左子树比右子树高度低）
                if leftHeight-rightHeight>1 :
                    leftChildLeftHeight = MyBinaryTree.GetHeight(root.leftChild.leftChild)
                    leftChildRightHeight = MyBinaryTree.GetHeight(root.leftChild.rightChild)
                    if leftChildLeftHeight>leftChildRightHeight:
                        root = MyBinaryTree.LL(root,rootFather)
                    else:
                        root = MyBinaryTree.LR(root,rootFather)
            else:
                root.leftChild = MyBinaryTree.DelNode(nodeData,root.leftChild,root)
                #需要判断平衡状态
                leftHeight = MyBinaryTree.GetHeight(root.leftChild)
                rightHeight = MyBinaryTree.GetHeight(root.rightChild)
                #不平衡需要旋转（因为从一个平衡二叉树的左子树删除一个节点，不需要考虑右子树比左子树高度低）
                if rightHeight-leftHeight>1 :
                    rightChildLeftHeight = MyBinaryTree.GetHeight(root.rightChild.leftChild)
                    rightChildRightHeight = MyBinaryTree.GetHeight(root.rightChild.rightChild)
                    if rightChildRightHeight>rightChildLeftHeight:
                        root = MyBinaryTree.RR(root,rootFather)
                    else:
                        root = MyBinaryTree.RL(root,rootFather)

        return root

#定义一颗哈夫曼树
class HuffManTree(TreeBase):
    def __init__(self):
        self.root = None
        pass
    def CreateTree(self,arr):
        #首先由数组创建对应的树状节点
        treeNodeArr = []
        arrLen = len(arr)
        i = 0
        while(i<arrLen):
            node = TreeNode(arr[i])
            treeNodeArr.append(node)
            i = i+1

        def funTemp(a,b):
            if a.data<b.data:
                return a
            else:
                return b
        i = arrLen-1
        while(i>1):
            SortMoudle.SortUserDefFun(treeNodeArr,funTemp)

            node = TreeNode(treeNodeArr[i].data+treeNodeArr[i-1].data,treeNodeArr[i],treeNodeArr[i-1])
            treeNodeArr[i-1] = node 
            i = i-1

        self.root = node
            


# 测试用数据
#region 测试用数据
#...
#                  10
#        20                54
#    8        2       8        11
# 5     6   1   5   7   9   15  18
#...
def TestTree():
    a = TreeNode(5)
    b = TreeNode(6)
    c1 = TreeNode(8,a,b)
    
    a = TreeNode(1)
    b = TreeNode(5)
    c2 = TreeNode(2,a,b)
    
    a = TreeNode(7)
    b = TreeNode(9)
    c3 = TreeNode(8,a,b)
    
    a = TreeNode(15)
    b = TreeNode(18)
    c4 = TreeNode(11,a,b)

    t2_1 = TreeNode(20,c1,c2)
    t2_2 = TreeNode(54,c3,c4)

    root = TreeNode(10,t2_1,t2_2)

    return root


def TestTree_2():
    a = TreeNode(5)
    b = TreeNode(6)
    c1 = TreeNode(8,a,b)
    
    a = TreeNode(1)
    b = TreeNode(5)
    c2 = TreeNode(2,a,b)
    
    a = TreeNode(7)
    b = TreeNode(9)
    c3 = TreeNode(8,a,b)
    
    a = TreeNode(15)
    b = TreeNode(18)
    c4 = TreeNode(11,a,b)

    t2_1 = TreeNode(20,c1,None)
    t2_2 = TreeNode(54,None,c4)

    root = TreeNode(10,t2_1,t2_2)

    return root


def TestArr():
    arr = [10,20,54,8,2,8,11,5,6,1,5,7,9,15,18]
    return arr

#endregion

#树的前、中、后序遍历
#region 树的前、中、后序和层序遍历
def PreOrder(root):
    if root == None:
        return
    #pass
    print(root.data,end = ",")
    PreOrder(root.leftChild)
    PreOrder(root.rightChild)
#后序遍历
def PostOrder(root):
    if root == None:
        return
    PostOrder(root.leftChild)
    PostOrder(root.rightChild)
    print(root.data,end = ",")

#中序遍历
def MidOrder(root):
    if root == None:
        return
    MidOrder(root.leftChild)
    print(root.data,end = ",")
    MidOrder(root.rightChild)

#层序遍历
def LevelOrder(root):
    list = []
    listIndex = 0
    list.append(root)
    while(listIndex<len(list)):
        print("%d,"%(list[listIndex].data),end = "")
        if list[listIndex].leftChild != None:
            list.append(list[listIndex].leftChild)
        if list[listIndex].rightChild != None:
            list.append(list[listIndex].rightChild)
        listIndex = listIndex+1
            
    #listIndex = 0;
    #listLen = len(list)
    #while(listIndex<listLen):

#以树状格式打印出树
def PrintTree(root):

    if root == None:
        print("No Tree")
        return
    list = []
    listIndex = 0
    list.append(root)
    while(listIndex<len(list)):
        if list[listIndex].leftChild != None:
            list.append(list[listIndex].leftChild)
        if list[listIndex].rightChild != None:
            list.append(list[listIndex].rightChild)
        listIndex = listIndex+1
    
    treeCount = listIndex*2

    list = []
    listIndex = 0
    list.append(root)

    while(listIndex<treeCount):
        #print("%d,"%(list[listIndex].data),end = "")
        #if list[listIndex].data != "  " and ((list[listIndex].leftChild != None) or (list[listIndex].rightChild != None)):
        #if list[listIndex].data != "  ":
        if list[listIndex].leftChild != None:
            list.append(list[listIndex].leftChild)
        else:
            list.append(TreeNode("  "))
        if list[listIndex].rightChild != None:
            list.append(list[listIndex].rightChild)
        else:
            list.append(TreeNode("  "))
        listIndex = listIndex+1

    listIndex = 0
    listLen = len(list)
    listMaxNum = (listLen+1)/2
    #listMaxNum = (listLen+1)
    levelNum = 0
    levelMax = 1
    #print(listMaxNum)

    while(listIndex<listLen):
        levelNum = levelNum + 1
        speaceNum = listMaxNum*3/2

        i = 0
        while(i<speaceNum-3):
            print(" ",end = "")
            i = i + 1
        print("%3s"%(list[listIndex].data),end = "")
        i =0
        while(i<speaceNum):
            print(" ",end = "")
            i = i + 1
        listIndex = listIndex + 1
        
        if levelNum < levelMax:
            pass
        else:
            listMaxNum = listMaxNum/2
            levelMax = levelMax*2
            levelNum = 0
            print("")
            speaceNum = listMaxNum*3/2
    print("")
    
#endregion


if __name__ == "__main__":
    print("Run File TreeModel:")
    pass